// m

// 给定两个整数m和n，代表大小为m*n的棋盘，一个机器人位于棋盘左上角的位置，机器人每次只能向右，或者向下移动一步
// 要求：计算出机器人从棋盘左上角到达棋盘右下角一共有多少条不同的路径

// 解题思路: 动态规划
// 1. 划分阶段， 按照路径的结尾位置（行位置，列位置组成的二维坐标）进行阶段划分
// 2. 定义状态，定义状态dp[i][j]为：从左上角到达[i, j]位置的路径数量
// 3. 状态转移方程，因为我们每次只能向右或者向下移动一步，因此想要走到i,j,只能从(i-1, j)向下走一步走过来，或者从（i, j - 1）向右走一步过来
//    所以可以写出状态转移方程为：dp[i][j] = dp[i-1][j] + dp[i][j-1]，此时i > 0,j > 0
// 4. 初始条件
//    1. 从左上角走到（0,0）只有一种方法，即dp[0][0] = 1
//    2. 第一行元素只有一条路径（即只能通过前一个元素向右走得到），所以dp[0][j] = 1
//    3. 同理，第一列元素只有一条路径（即只能通过前一个元素向下走得到），所以dp[i][0] = 1
// 5. 最终结果
//   根据状态定义，最终结果dp[m-1][n-1],及左上角到右下角（m-1, n-1）位置的路径数量

// 复杂度分析
// 时间复杂度：O(m*n)
// 空间复杂度：O(m*n)

function uniquePaths(m, n) {
    let dp = new Array(m).fill(0).map(() => new Array(n).fill(0))

    for (let i = 0; i < m; i++) {
        dp[i][0] = 1
    }
    for (let i = 0; i < n; i++) {
        dp[0][i] = 1
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
}
let m = 3, n = 7
console.log(uniquePaths(m, n));